#!/usr/bin/env python3

from numpy import random
import time


class ListNode:
    """
    Linked list node
    """

    def __init__(self, data):
        self.prev = None
        self.next = None
        self.data = data

    def __repr__(self):
        return '<ListNode ' + repr(self.data) + '>'


class DLList(object):
    """
    Doubly-linked list
    """

    def __init__(self, seq=None):
        self.list = None
        node = None
        if seq is not None:
            for x in seq:
                if self.list is None:
                    self.list = ListNode(x)
                    node = self.list
                else:
                    node.next = ListNode(x)
                    node.next.prev = node
                    node = node.next

    def find(self, data):
        node = self.list
        while node is not None:
            if node.data == data:
                return node.data
            node = node.next
        else:
            return None

    @staticmethod
    def delete(node):
        if node.prev is not None:
            node.prev.next = node.next
        if node.next is not None:
            node.next.prev = node.prev
        node.prev = None
        node.next = None
        return node

    def print_list(self):
        node = self.list
        while node.next is not None:
            print('{0} -> '.format(node.data), end='')
            node = node.next
        print(node.data)


class MTFList(DLList):
    """
    Liked list with "move to front" euristics.
    """

    def access(self, element):
        node = self.list
        if node is None:
            print('empty list')
        else:
            while node is not None and node.data != element:
                node = node.next
            if node is None:
                return None
            else:
                if node is not self.list:
                    self.delete(node)
                    self.list.prev = node
                    node.next = self.list
                    self.list = node
                return node.data


if __name__ == "__main__":
    lstdata = list(range(1, 10 ** 4 + 1))
    random.shuffle(lstdata)
    lst = MTFList(lstdata)
    srch = [random.randint(1, 10 ** 4) for i in range(10 ** 4)]
    t_start = time.time()
    for x in srch:
        if not lst.access(x):
            print('{0} is not in range(1, {1})'.format(x, 1 + len(lstdata)))
            print('check:', x, 'in lstdata =', x in lstdata)
    t_stop = time.time()
    print('mtf list:\t{0}'.format(t_stop - t_start))

    srch_freq = dict()
    for x in srch:
        if srch_freq.get(x, None) is None:
            srch_freq[x] = 1
        else:
            srch_freq[x] += 1
    lstdata.sort(key=lambda x: srch_freq.get(x, -1), reverse=True)
    lst = DLList(lstdata)
    t_start = time.time()
    for x in srch:
        if not lst.find(x):
            print('x =', x, 'not found in lst (sorted)')
    t_stop = time.time()
    print('sorted list:\t{0}'.format(t_stop - t_start))

    print('\nworst-case tests')
    del lst, srch, srch_freq
    lstdata.sort()
    lst = MTFList(reversed(lstdata))
    t_start = time.time()
    for x in range(1, len(lstdata) + 1):
        if lst.access(x) is None:
            print('{0} is not in lstdata (range(1, {1})) (MTF)'.format(x, 1 + len(lstdata)))
    t_stop = time.time()
    print('mtf list:\t\t{0}'.format(t_stop - t_start))

    lst = DLList(reversed(lstdata))
    t_start = time.time()
    for x in range(1, len(lstdata) + 1):
        if lst.find(x) is None:
            print('{0} is not in lstdata (range(1, {1})) (usual dl-list)'.format(x, 1 + len(lstdata)))
    t_stop = time.time()
    print('doubly-linked list:\t{0}'.format(t_stop - t_start))
